﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AstarTest
{
    class Maze
    {
        public int Rows { get; set; }
        public int Columns { get; set; }
	    private Square[,] elements;
	    private Square goal;
	    private const string CLOSED_TOP = "+ - ";
        private const string OPEN_TOP = "+   ";
        private const string CLOSED_LEFT = "|   ";
        private const string CLOSED_LEFT_PATH = "| . ";
        private const string CLOSED_LEFT_START = "| S ";
        private const string CLOSED_LEFT_GOAL = "| G ";
        private const string OPEN_LEFT = "    ";
        private const string OPEN_LEFT_PATH = "  . ";
        private const string OPEN_LEFT_START = "  S ";
        private const string OPEN_LEFT_GOAL = "  G ";

	    private List<Square> opened = new List<Square>();
	    private List<Square> closed = new List<Square>();
	    private List<Square> bestList = new List<Square>();

	    public Maze(int Rows, int Columns) {

		    this.Rows = Rows;
		    this.Columns = Columns;
		    elements = new Square[Rows, Columns];
		    init();
	    }

	    private void init() {

		    createSquares();
		    setStartAndGoal();
		    generateAdjacencies();
	    }

	    private void setStartAndGoal() {

		    elements[0, 0].IsStart = true;
		    Random random = new Random();
		    int goalX = 0, goalY = 0;
		    while (goalX == 0 && goalY == 0) {
			    goalX = random.Next(Rows);
                goalY = random.Next(Columns);
		    }
		    goal = elements[goalX, goalY];
            goal.IsEnd = true;
	    }

	    private void generateAdjacencies() {

		    for (int i = 0; i < Rows; i++) {
			    for (int j = 0; j < Columns; j++) {
				    elements[i, j].calculateAdjacencies();
			    }
		    }
	    }

	    private void createSquares() {

		    for (int i = 0; i < Rows; i++) {
			    for (int j = 0; j < Columns; j++) {
				    elements[i, j] = new Square(i, j, this);
			    }
		    }
	    }

	    public Square getSquare(int x, int y) {

		    return elements[x, y];
	    }

	    public void setSquare(Square square) {

		    elements[square.X, square.Y] = square;
	    }

	    public void draw() {
            Console.WriteLine("Drawing maze");

            //for (int i = 0; i < Rows; i++)
            //{
            //    for (int j = 0; j < Columns; j++)
            //    {
            //        Square square = elements[i, j];
            //        if (square.IsStart)
            //            Console.Write("S");
            //        else if (square.IsEnd)
            //            Console.Write("E");
            //        else if (this.bestList.Contains(square))
            //            Console.Write(".");
            //        //Console.WriteLine("X=" + square.X + "  Y=" + square.Y);
            //        else Console.Write("#");
            //    }
            //    Console.WriteLine();
            //}

            drawContents();
            drawBorder();
	    }

	    private void drawContents() {

		    for (int i = 0; i < Rows; i++) {
			    for (int j = 0; j < Columns; j++) {
				    Square square = elements[i, j];
				    drawTop(square);
			    }
			    Console.WriteLine("+");

			    for (int j = 0; j < Columns; j++) {
				    Square square = elements[i, j];
				    drawLeft(square);
			    }
			    Console.WriteLine("|");
		    }
	    }

	    private void drawLeft(Square square) {

		    int x = square.X;
		    int y = square.X;

		    if (y - 1 < 0) {
			    if (square.IsStart) {
				    Console.Write(CLOSED_LEFT_START);
				    return;
			    }

			    if (square.IsEnd) {
				    Console.Write(CLOSED_LEFT_GOAL);
				    return;
			    }

			    if (bestList.Contains(square)) {
				    Console.Write(CLOSED_LEFT_PATH);
				    return;
			    }
			    Console.Write(CLOSED_LEFT);
			    return;
		    }

		    foreach (Square neighbor in square.Adjacencies) {
			    if (neighbor.X == x && neighbor.Y == y - 1) {
				    if (square.IsEnd) {
					    Console.Write(OPEN_LEFT_GOAL);
					    return;
				    }
				    if (bestList.Contains(square)) {
					    Console.Write(OPEN_LEFT_PATH);
					    return;
				    }
				    Console.Write(OPEN_LEFT);
				    return;
			    }
		    }

		    if (square.IsEnd) {
			    Console.Write(CLOSED_LEFT_GOAL);
			    return;
		    }

		    if (bestList.Contains(square)) {
			    Console.Write(CLOSED_LEFT_PATH);
			    return;
		    }
		    Console.Write(CLOSED_LEFT);

	    }

	    private void drawTop(Square square) {

		    int x = square.X;
		    int y = square.Y;

		    if (x == 0) {
			    Console.Write(CLOSED_TOP);
			    return;
		    }

		    foreach (Square neighbor in square.Adjacencies) {
			    if (neighbor.X == x - 1 && neighbor.Y == y) {
				    Console.Write(OPEN_TOP);
				    return;
			    }
		    }

		    Console.Write(CLOSED_TOP);
	    }

	    private void drawBorder() {

		    for (int i = 0; i < Columns; i++) {
			    Console.Write(CLOSED_TOP);
		    }
		    Console.WriteLine("+");
	    }

	    public void findBestPath() {

		    Console.WriteLine("Calculating best path...");
		    HashSet<Square> adjacencies = elements[0, 0].Adjacencies;
		    foreach (Square adjacency in adjacencies) {
			    adjacency.Parent = elements[0, 0];
			    if (adjacency.IsStart == false) {
				    opened.Add(adjacency);
			    }
		    }

		    while (opened.Count > 0) {
			    Square best = findBestPassThrough();
			    opened.Remove(best);
			    closed.Add(best);
			    if (best.IsEnd) {
				    Console.WriteLine("Found Goal");
				    populateBestList(goal);
				    draw();
				    return;
			    } else {
				    HashSet<Square> neighbors = best.Adjacencies;
				    foreach (Square neighbor in neighbors) {
					    if (opened.Contains(neighbor)) {
						    Square tmpSquare = new Square(neighbor.X,
								    neighbor.Y, this);
						    tmpSquare.Parent = best;
						    if (tmpSquare.getPassThrough(goal) >= neighbor
								    .getPassThrough(goal)) {
							    continue;
						    }
					    }

					    if (closed.Contains(neighbor)) {
						    Square tmpSquare = new Square(neighbor.X,
								    neighbor.Y, this);
						    tmpSquare.Parent = best;
						    if (tmpSquare.getPassThrough(goal) >= neighbor
								    .getPassThrough(goal)) {
							    continue;
						    }
					    }
					
					    neighbor.Parent = best;

					    opened.Remove(neighbor);
					    closed.Remove(neighbor);
                        opened.Insert(0, neighbor);
				    }
			    }
		    }

		    Console.WriteLine("No Path to goal");
	    }

	    private void populateBestList(Square square) {

		    bestList.Add(square);
		    if (square.Parent.IsStart == false) {
                populateBestList(square.Parent);
		    }

		    return;
	    }

	    private Square findBestPassThrough() {

		    Square best = null;
		    foreach (Square square in opened) {
			    if (best == null
					    || square.getPassThrough(goal) < best.getPassThrough(goal)) {
				    best = square;
			    }
		    }

		    return best;
	    }
    }
}
